#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>

#include "segger.h"
#include "charset.h"
#include "mylog.h"

enum					SLAB_KEY{SLAB_TOK=0, SLAB_CHUNK, SLAB_MM, SLAB_MMH};
static const unsigned	SLOT_SIZE[] =	{sizeof(struct tok), sizeof(struct chunk), sizeof(struct tok), sizeof(struct list_head), 0};

segger * segger_new(dat * datp)
{
    if(datp == NULL){
        return NULL;
    }
#ifndef NDEBUG
        logit(LV_LOG, "segger new ...");
#endif
	segger * p = (segger *)malloc(sizeof(struct segger));
	p->datp = datp;

	p->buf = NULL; //wait for input
	p->len = 0;
	p->off = 0;
	p->slabp = slab_create();
    if(p->slabp < 0){
#ifndef NDEBUG
        logit(LV_ERROR, "slab new");
#endif
		free(p);
        return NULL;
    }
	int i = 0;
	while(SLOT_SIZE[i]){
		if(slab_add(p->slabp, SLOT_SIZE[i], i) < 0){
			free(p);
			slab_destroy(p->slabp);
			return NULL;
		}
		i ++;
	}
	p->mm = vla_new(sizeof(struct list_head *));
    if(p->mm == NULL){
#ifndef NDEBUG
		logit(LV_ERROR, "mm new");
#endif
		free(p);
		slab_destroy(p->slabp);
        return NULL;
    }
	INIT_LIST_HEAD(&p->res);
	return p;
}

int segger_free(segger *p)
{
	if(p == NULL){
		return -1;
	}
	slab_destroy(p->slabp);
	vla_free(p->mm);
	INIT_LIST_HEAD(&p->res);
	p->buf = NULL;
	p->len = 0;
	p->off = 0;
	free(p);
#ifndef NDEBUG
	logit(LV_LOG, "segger free ...");
#endif
	return 0;
}

static tok * tok_new(slab *p, unsigned char key, unsigned short len, unsigned int tag, unsigned int freq)
{
	assert(p != NULL && len != 0);
	tok * t = slab_alloc(p, sizeof(struct tok), key);
	if(t == NULL){
		return NULL;
	}
	t->len = len;
	t->tag = tag;
	t->freq = freq;
	return t;
}

#ifndef NDEBUG
static int log_tok(unsigned char level, segger * p, tok * t, unsigned int * offp)
{
	assert(p != NULL && offp != NULL);
	if(t == NULL){
		return -1;
	}
	unsigned int off = *offp;
	if(off == 0){
		struct list_head * l = NULL;
		tok * tt = NULL;
		list_for_each(l, &p->res){
			tt = list_entry(l, tok , list);
			off += tt->len;
		}
	}
	char out[1024] = {0};
	strncpy(out, p->buf + off, t->len);
	out[t->len] = '\0';
	logit(level, "  [%p(%d-%d)]%s", t, t->len, t->freq, out);
	off += t->len;
	*offp = off;
	return 0;
}

static int log_cur_tok(unsigned char level, segger * p, thunk * tk)
{
	unsigned int off = 0;
	struct list_head *l = NULL;
	chunk *c = NULL;
	list_for_each(l, &tk->chunks){
		off = 0;
		c = list_entry(l, chunk, list);
		logit(level, "<<<");
		log_tok(level, p, c->t1, &off);
		log_tok(level, p, c->t2, &off);
		log_tok(level, p, c->t3, &off);
	}
	return 0;
}
#endif

int push_mm(segger * p, unsigned int off, unsigned short len, unsigned int tag, unsigned int freq)
{
	assert(p != NULL && len > 0 && off >= p->off);
	tok * t = tok_new(p->slabp, SLAB_MM, len, tag, freq);
	if(t == NULL){
		return -1;
	}
	struct list_head **m = vla_set(p->mm, off - p->off);
	if(m == NULL){
		return -2;
	}
	if(*m == NULL){
		*m = slab_alloc(p->slabp, sizeof(struct list_head), SLAB_MMH);
		if(*m == NULL){
			return -3;
		}
		INIT_LIST_HEAD(*m);
	}
	list_add_tail(&t->list, *m);
	return 0;
}

int push_tok(segger * p, unsigned short len, unsigned int tag, unsigned int freq)
{
	assert(p != NULL && len > 0);
	tok * t = tok_new(p->slabp, SLAB_TOK, len, tag, freq);
	if(t == NULL){
		return -1;
	}
	list_add_tail(&t->list, &p->res);
	return 0;
}


int push_chunk(thunk *tk, slab *s, unsigned short size, tok *t1, tok *t2, tok *t3)
{
	assert(tk != NULL && s != NULL && t1 != NULL);
	unsigned short len = t1->len;
	switch(size){
	case 3: len += t3->len;
	case 2: len += t2->len;
	}
	if(len < tk->max_len){
		return 1;
	}else if(len > tk->max_len){
		tk->max_len = len;
		INIT_LIST_HEAD(&tk->chunks);
		tk->size = 0;
	}
	chunk * c = slab_alloc(s, sizeof(struct chunk), SLAB_CHUNK);
	if(c == NULL){
		return -1;
	}
	memset(c, 0, sizeof(struct chunk));
	c->t1 = t1;
	c->t2 = t2;
	c->t3 = t3;
	c->len = len;
	c->size = size;
	list_add_tail(&c->list, &tk->chunks);
	tk->size ++;
	return 0;
}

double chunk_avl(chunk * c)
{
	assert(c != NULL);
	return (double)1.0 * c->len / c->size;
}

//variance D(x) = E{[X-E(X)]^2}
//return -D(x) * size = -[X-E(X)]^2
double chunk_var(chunk *c)
{
	assert(c != NULL);
	double avl = (double)1.0 * c->len / c->size;
	double diff = c->t1->len - avl;
	double var = diff*diff;
	switch(c->size){
	case 3: diff = c->t3->len - avl; var += diff*diff;
	case 2: diff = c->t2->len - avl; var += diff*diff;
	}
	return 0 - var;
}

double chunk_df(chunk *c)
{
	assert(c != NULL);
	double df = log((double)FREQ(c->t1->freq))*100;
	switch(c->size){
	case 3: df += log((double)FREQ(c->t3->freq))*100;
	case 2: df += log((double)FREQ(c->t2->freq))*100;
	}
	return df;
}

typedef double (*rule)(chunk *c);
int onrule(struct list_head * chunks, rule r)
{
	assert(chunks != NULL && r != NULL);
	struct list_head cand;//candidate list
	INIT_LIST_HEAD(&cand);
	int num = 0;
	double v = 0.0;
	double v_max = 0.0;
	struct list_head *l = NULL;
	chunk *c = NULL;
	list_for_each(l, chunks){
		c = list_entry(l, chunk, list);
		v = r(c);
		if(v > v_max + 0.001 || num == 0){
//			printf("%lf > %lf \n", v, v_max);
//			printf("(%x) > (%x) \n", v, v_max);
			v_max = v;
			INIT_LIST_HEAD(&cand);
			num = 0;
		}else if(v < v_max - 0.001){
			continue;
		}
		l = l->prev;
		list_del(&c->list);
		list_add_tail(&c->list, &cand);
		num ++;
	}
	LIST_HEAD_MOVE(chunks, &cand);
	return num;
}

//oov-foreign return0: no oov; >0 have oov
int oov_forn(segger *p, tok *t)
{
	if(p->res.next == &p->res){
		return 0;
	}
	tok * t1 = list_entry(p->res.prev, tok, list);
	if(t1->tag & _FORN_){
		t1->len += t->len;
		return t->len;
	}
	return 0;
}

//oov-suffix(location) return 0: no oov >0 have oov
int oov_ns(segger *p, tok *t)
{
	if(p->res.next == &p->res){
		return 0;
	}
	tok * t1 = list_entry(p->res.prev, tok, list);
	tok * t2 = NULL;
	if(t1->len != 3 && t1->len != 6){
		return 0;
	}else if( t1->len == 3 && t1->list.prev != &p->res && (t2 = list_entry(t1->list.prev, tok, list)) && t2->len == 3){
		if(!(t1->tag & _z_) || !(t2->tag & _z_) || (t1->tag & _P_) || (t2->tag & _P_)){
			return 0;
		}
		t2->len += (t1->len + t->len);
		t2->tag = _N_|_z_;
		list_del(&t1->list);
	}else{
		if(!(t1->tag & _z_) || (t1->tag & (_P_|_M_))){
			return 0;
		}
		t1->len += t->len;
		t1->tag = _N_|_z_;
	}
	return t->len;
}

//oov-prefix(human name) return 0: no oov >0 have oov
int oov_nr(segger *p, tok *t, tok *tn)
{
	assert(p->res.next != &p->res);
	if( p->hoov_flag == 1 && ((t->tag & _NRRGH_) || (t->tag & (_M_|_E_|_S_))) ){
		tok * t1 = list_entry(p->res.prev, tok, list);
		assert(t1->len == 3 && list_entry(t1->list.prev, tok, list)->len == 3);
		t1->len += 3;
		t1->tag = _N_|_z_;
		list_del(t1->list.prev);
		p->hoov_flag = 0;
	}else if(p->hoov_flag == 2 && t->len == 3 && tn == NULL && !(t->tag & _P_)){
		tok * t1 = list_entry(p->res.prev, tok, list);
		t1->len += t->len;
		t1->tag = _N_|_z_;
		p->hoov_flag = 0;
		return t->len;
	}else if(p->hoov_flag > 1 && t->len == 3 && tn != NULL && !(t->tag & _P_)){
		p->hoov_flag --;
	}else{
		p->hoov_flag = 0;
	}
	return 0;
}

int push2tok(segger *p, chunk * c)
{
	assert(p != NULL && c != NULL && c->size > 0 && c->t1 != NULL);
/* oov here
 * if cur is _NSSUF_, look back 2 tok
 * if cur is _NRPRE_, set a flag for later
 * if cur is _FORN_, set a flag for later
*/

/* ----------- set ----------- */
	if((c->t1->tag & _NSSUF_) && oov_ns(p, c->t1) > 0){
		p->hoov_flag = 0;
		goto OUT;
	}else if(p->hoov_flag == 0){
		if((c->t1->tag & _FORN_) && (c->t1->tag & _NRPRE_)){
			p->hoov_flag = 5;//if follow is not forn, hoov_flag reduce to 2 and then oov_nr
		}else if(c->t1->tag & _FORN_){
			p->hoov_flag = 4;//foreign
		}else if((c->t1->tag & _NRPRE_)){
			p->hoov_flag = 3;//hp accept 2 name followed and 1 right edge
		}
		goto PUSH;
	}else if(p->hoov_flag > 3 && !(c->t1->tag & _FORN_)){
		if(p->hoov_flag == 5){
			p->hoov_flag = 3;
		}else if(c->t1->tag & _NRPRE_){
			p->hoov_flag = 3;
			goto PUSH;
		}else{
			p->hoov_flag = 0;
		}
	}
/* ----------- oov ----------- */
	if(p->hoov_flag > 3 && oov_forn(p, c->t1) > 0){
		goto OUT;
	}else if(p->hoov_flag > 0 && oov_nr(p, c->t1, c->t2) > 0){
		goto OUT;
	}

PUSH:
	if(push_tok(p, c->t1->len, c->t1->tag, c->t1->freq) < 0){
		return -1;
	}
OUT:
	return c->t1->len;
}

int pick_chunk(thunk *tk, segger *p)
{
	assert(tk != NULL && p != NULL);
	if(tk->size == 1){ //only one
		goto RET;
	}
/*
#ifndef NDEBUG
		logit(LV_DEBUG, "len");
		log_cur_tok(LV_DEBUG, p, tk);
#endif
*/

	//rule2
	tk->size = onrule(&tk->chunks, chunk_avl);
	if(tk->size <= 0){
		return -1;
	}else if(tk->size == 1){ //only one
		goto RET;
	}
/*
#ifndef NDEBUG
		logit(LV_DEBUG, "avl");
		log_cur_tok(LV_DEBUG, p, tk);
#endif
*/

	//rule3
	tk->size= onrule(&tk->chunks, chunk_var);
	if(tk->size <= 0){
		return -2;
	}else if(tk->size == 1){ //only one
		goto RET;
	}
/*
#ifndef NDEBUG
		logit(LV_DEBUG, "var");
		log_cur_tok(LV_DEBUG, p, tk);
#endif
*/

	//rule4
	tk->size = onrule(&tk->chunks, chunk_df);
	
	if(tk->size <= 0){
		return -3;
	}else if(tk->size > 1){ //only one
/*
#ifndef NDEBUG
		log_cur_tok(LV_LOG, p, tk);
#endif
*/
	}
RET:
/*
#ifndef NDEBUG
		log_cur_tok(LV_DEBUG, p, tk);
#endif
*/
	return push2tok(p, list_entry(tk->chunks.prev, chunk, list));
}

int mmseg(segger * p)
{
#define _PUSH(n,t1,t2,t3)	do{ if(push_chunk(&tk, p->slabp, (n), (t1), (t2), (t3)) < 0){ret = -1;goto RET;} } while(0)
#define PUSH1(t1)			_PUSH(1,t1,NULL,NULL);
#define PUSH2(t1,t2)		_PUSH(2,t1,t2,NULL);
#define PUSH3(t1,t2,t3)		_PUSH(3,t1,t2,t3);
#define MMEMPTY(m,i)		(((m) = vla_get(p->mm, (i))) == NULL || *(m) == NULL || list_empty(*(m)))
	assert(p != NULL);
	int ret = 0;
	int i1 = 0;
	int i2 = 0;
	int i3 = 0;
	struct list_head **m1 = NULL;
	struct list_head **m2 = NULL;
	struct list_head **m3 = NULL;
	struct list_head *l1 = NULL;
	struct list_head *l2 = NULL;
	struct list_head *l3 = NULL;
	tok * t1 = NULL;
	tok * t2 = NULL;
	tok * t3 = NULL;
	thunk tk;
	while(i1 < VLA_SIZEOF(p->mm)){
		//1st
		tk.max_len = 0;
		tk.size = 0;
		INIT_LIST_HEAD(&tk.chunks);
		slab_clear(p->slabp, sizeof(struct chunk), SLAB_CHUNK);//chunk.clear
	
		t1 = NULL;
		if(MMEMPTY(m1, i1)){
			break;
		}
		list_for_each(l1, *m1){
			t1 = list_entry(l1, tok, list);
			i2 = i1 + t1->len;
			//2nd
			t2 = NULL;
			if(MMEMPTY(m2, i2)){
				PUSH1(t1);
				continue;
			}
			list_for_each(l2, *m2){
				t2 = list_entry(l2, tok, list);
				i3 = i2 + t2->len;
				//3rd
				t3 = NULL;
				if(MMEMPTY(m3, i3)){
					PUSH2(t1,t2);
					continue;
				}
				{
					l3 = (*m3)->prev;// the longest one
					t3 = list_entry(l3, tok, list);
					PUSH3(t1,t2,t3);
				}//3
			}//2
		}//1
		ret = pick_chunk(&tk, p);
		if(ret <= 0){
			goto RET;
		}
		i1 += ret;
#ifndef NDEBUG
	//to log r
#endif
	}//while
RET:
	vla_clear(p->mm);
	slab_clear(p->slabp, sizeof(struct tok), SLAB_MM); 
	slab_clear(p->slabp, sizeof(struct list_head), SLAB_MMH);
	return ret<0?ret:i1;
#undef _PUSH
#undef PUSH1
#undef PUSH2
#undef PUSH3
#undef MMEMPTY
}

//get next result
const char * segger_next_res(segger * p, unsigned int * lenp)
{
	if(p == NULL || lenp == NULL){
		return 0;
	}
	if(p->res_ == NULL){
		p->off = 0;
		p->res_ = p->res.next;
	}
	if(p->res_ == &p->res){
		*lenp = 0;
		return NULL;
	}
	tok * t = list_entry(p->res_, tok, list);
	//FIXME: shit algorithm
	if(DIV1(t->freq)){
		if(p->div_flag == 0){//1st
			*lenp = DIV1(t->freq);
			p->div_flag = 1;
		}else if(p->div_flag == 1){//2nd
			*lenp = DIV2(t->freq);
			p->div_flag = 2;
			if(*lenp == 0){
				*lenp = t->len - DIV1(t->freq);
				p->res_ = p->res_->next;
				p->div_flag = 0;
			}
		}else if(p->div_flag == 2){//3rd
			*lenp = t->len - DIV1(t->freq) - DIV2(t->freq);
			p->res_ = p->res_->next;
			p->div_flag = 0;
		}else{
			//error
		}
	}else if(DIV2(t->freq)){
		if(p->div_flag == 0){//1st
			*lenp = t->len - DIV2(t->freq);
			p->div_flag = 1;
		}else if(p->div_flag == 1){//2nd
			*lenp = DIV2(t->freq);
			p->res_ = p->res_->next;
			p->div_flag = 0;
		}else{
			//error
		}
	}else{
		*lenp = t->len;
		p->res_ = p->res_->next;
	}
	assert(*lenp > 0);
	p->off += *lenp;
	if(p->off > p->len){
#ifndef NDEBUG
		logit(LV_ERROR, "off: %u, len: %u", p->off, p->len);
#endif
		return NULL;
	}
	return p->buf + p->off - *lenp;
}

//only accept utf8 C-string
int segger_do(segger * p, char * input, unsigned int len)
{
	if(p == NULL || input == NULL || len == 0 || len > SEG_LEN_MAX ){
		return SEG_INPUT_ERR;
	}
	p->buf = input;
	p->len = len;
	p->off = 0;
	p->res_ = NULL;
	p->div_flag = 0;
	INIT_LIST_HEAD(&p->res);
	slab_clear(p->slabp, sizeof(struct tok), SLAB_TOK);
	
	int ret = 0;
	unsigned short code = 0;
	unsigned char st = _u_;		//state of cur char
	unsigned char st_ = _u_;	//state of next char
	int clen = 0;				//len of cur char
	int clen_ = 0;				//len of next char
	unsigned int coff_ = 0;		//next char off
	unsigned int mes = 0;		//begin of mn; used to push whole block to mm
	unsigned char mes_st = 0;
	dat_res dres;				//dat result

/*
* |buf     |off              |coff_
*  ----------------------------------------------
* |   ...  |     |     | len |len_ |     |  ...  |
*  --------^-----------------^-------------------
*   tokened|           readed|
*                             
*/
	//prepare
	clen_ = utf8decode(p->buf, &code);
	if(clen_ < 0){
		return SEG_DECODE_ERR;
	}else if(clen_ == 0){
		return SEG_EMPTY;
	}
	st_ = tag(code);
	while(clen_){	//untile next clen = 0 -> '\0';
		st = st_;
		clen = clen_;
		coff_ += clen;//next c off
		if(coff_ > p->len){
			break;
		}
		clen_ = utf8decode(p->buf + coff_, &code);
		if(clen_ < 0){
			return SEG_DECODE_ERR;
		}
		st_ = tag(code);

		switch(st){
		case _z_:	//st(z)->each->push mm->end->seg->token	
		case _n_:
		case _f_:
			//dat and push mm
			ret = dat_fetch(p->datp, p->buf + coff_ - clen, -1, &dres);
			if(ret < 0){
				return SEG_DATFETCH_ERR + ret;
			}
			//single push avoid last nf dup push
			if(dres.num == 0 && (!(st & (_m_|_e_|_s_)) || (st_ & (_m_|_e_|_s_))) && push_mm(p, coff_ - clen, clen, (unsigned int)st, 1) < 0){
				return SEG_PUSHMM_ERR;
			}
			int bpushed = 0;
			int i = 0;
			for(i=0; i<dres.num; i++){
				assert(dres.item[i].len > 0);
				ret = push_mm(p, coff_ - clen, dres.item[i].len, dres.item[i].tag, dres.item[i].freq);
				if(ret < 0){
					return SEG_PUSHMM_ERR + ret;
				}
				//m-oov at the next time
				if( (dres.item[i].tag & _Q_) && (mes_st & _m_) ){
					ret = push_mm(p, mes, coff_ - clen - mes + dres.item[i].len, _z_|_M_|_Q_, 1/*DIV2AT(1, dres.item[i].len)*/);
					if(ret < 0){
						return SEG_PUSHMM_ERR + ret;
					}
					bpushed = 1;
				}
			}
			if(bpushed != 0){
				mes_st = 0;
			}
		case _m_:
		case _e_:
		case _s_:	//st(sme)->end->token
			//st not Q push and not m e s || mes_st is m e but st is n || mes_st is n st is m e
			//push not include this char
			if( (mes_st != 0 && !(st & (_m_|_e_|_s_))) || 
					((mes_st == _m_ || mes_st == _e_) && ((st & _z_) && (st & _m_))) || 
					((mes_st == _n_) && (!(st & _z_) || (st & _e_))) ){
				ret = push_mm(p, mes, coff_ - clen - mes, _z_|mes_st , 1);
				if(ret < 0){
					return SEG_PUSHMM_ERR + ret;
				}
				mes_st = 0;
			}
			//init mes must keep the sequece
			if((st & _m_) && (st & _z_) && mes_st == 0){
				mes = coff_ - clen;
				mes_st = _n_;
			}
			if(st & _m_ && mes_st == 0){
				mes = coff_ - clen;
				mes_st = _m_;
			}
			if(st & (_e_|_s_)){
				if(mes_st == 0){
					mes = coff_ - clen;
				}
				mes_st = _e_;
			}
			if(st_ & (_z_|_m_|_e_|_s_)){
				continue;
			}
			//st_ not zmes push // push include this char
			if( mes_st != 0 ){
				ret = push_mm(p, mes, coff_ - mes, _z_|st, 1);
				if(ret < 0){
					return SEG_PUSHMM_ERR + ret;
				}
			}
			mes_st = 0;
			ret = mmseg(p);//seg time
			if(ret < 0){ 
#ifndef NDEBUG
				logit(LV_ERROR, "push len %u + %d != %u", p->off, ret, coff_);
#endif
				return SEG_MMSEG_ERR + ret;
			}
			if(p->off + ret != coff_){
#ifndef NDEBUG
				logit(LV_ERROR, "wrong push %u + %d != %u", p->off, ret, coff_);
#endif
				return SEG_TOKCRUSH_ERR;
			}
			p->off = coff_;
			break;
		case _d_:	//st(d)->each->token
			if(push_tok(p, clen, st, 0) < 0){
				return SEG_PUSHTOK_ERR;
			}
			p->hoov_flag = 0;
			p->off = coff_;
			break;
		case _l_:	//st(l)->end->token
			if(st_ & _l_){
				continue;
			}
			if(push_tok(p, coff_ - p->off, st, 0) < 0){
				return SEG_PUSHTOK_ERR;
			}
			p->hoov_flag = 0;
			p->off = coff_;//next push pos
			break;
		case _u_:	//st(u)->end->token
			if(st_ == _u_){//_u_ is zero !!!
				continue;
			}
			if(push_tok(p, coff_ - p->off, st, 0) < 0){
				return SEG_PUSHTOK_ERR;
			}
			p->hoov_flag = 0;
			p->off = coff_;//next push pos
			break;
		default:
			break;
		}
		//only continue
	};
	//oov
	return 0;
}


#ifdef SEGGER_MAIN
int main(int argc, char ** argv)
{
	logon();
	init_codemap();
    dat * datp = dat_new();
    if(datp == NULL){
        return -1;
    }
    int ret = dat_load(datp, "/home/aaron/workspace/hiseg/dict/hidict.dat");
    if(ret < 0){
        return -2;
    }
	segger * p = segger_new(datp);
	if( p == NULL ){
		return -3;
	}
	char * s[] = {
					"明天就不一定了",
					"不\n",
					"其实，与中文用户相比，在中国进行计算机研究的人所付的代价还要大许多。",
					"而每往前走一步，都可能给中国的计算机专家们带来新的挑战，这场战斗旷日持久。",
					"技术流",
					"据说ｗｉｎｄｏｗｓ９５推出前，考虑到低性能电脑安装它的时间很长，微软公司曾向心理学家请教，怎样在安装等待过程中设计出活动的画面才能让用户不致焦躁。",
				};
	int i = 0;
	for(i=0; i<sizeof(s)/sizeof(char *); i++){
		int ret = segger_do(p, s[i], strlen(s[i]));
		if(ret < 0){
			printf("\n!!!!!ret: %d\n", ret);
			return i+1;
		}
		printf("\n");
		const char * res = NULL;
		unsigned len = 0;
		char out[1024*32] = {0};
		while((res = segger_next_res(p, &len)) != NULL){
			strncpy(out, res, len);
			out[len] = 0;
			printf("%s ", out);
		}
		printf("\n");
	}
	segger_free(p);
	dat_free(datp);
	free_codemap();
	logoff();
	return 0;
}
#endif
